package com.example.demo.leetcode.top100;

import java.util.Arrays;

/**
 * ******************************************************
 *
 * @author liugh9
 * @version 1.0
 * @classname _5盛最多水的容器
 * @description
 * @date 2023/06/03 22:34
 * <p>
 * ******************************************************
 */
public class _5盛最多水的容器 {


    public int maxArea1(int[] height) {
        int left = 0;
        int right = height.length - 1;

        int res = 0;

        while (left < right) {
            int curr = getArea(height, left, right);
            res = Math.max(res, curr);
            // 双指针技巧，移动较低的一边
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return res;
    }


    int[][] memo;

    public int maxArea(int[] height) {
        memo = new int[height.length][height.length];
        for (int[] item : memo) {
            Arrays.fill(item, -1);
        }
        return maxArea(height, 0, height.length - 1);

    }

    private int maxArea(int[] height, int i, int j) {
        if (i >= j) {
            return 0;
        }
        if (memo[i][j] != -1) {
            return memo[i][j];
        }
        int curr = getArea(height, i, j);
        int left = maxArea(height, i + 1, j);
        int right = maxArea(height, i, j - 1);
        memo[i][j] = Math.max(curr, Math.max(left, right));
        return memo[i][j];
    }

    private int getArea(int[] height, int i, int j) {
        return (j - i) * Math.min(height[i], height[j]);
    }
}
